package DataStructure.array;

/**
 * 75.颜色分类 https://leetcode.cn/problems/sort-colors
 * 题目简述：对一个包含0、1、2三种元素（颜色）的数组进行原地排序
 */
public class SortColors {

    /**
     * 思路一：利用快排中的partition方法 将数组划分为三个区域：0: [0, p0), 1: [p0, p1), 2: (p2, len-1]
     * 初始p0=0,p1=0,p2=len-1;p1开始扫描，每扫描到一个元素将其与对应区域的元素进行交换，并更新边界。越过p2结束
     */
    public void sortColors(int[] nums) {
        //循环不变量
        //0: [0, p0), 1: [p0, p1), 2: (p2, len-1]
        int p0=0, p1=0, p2=nums.length-1;
        while(p1 <= p2) {
            if(nums[p1] == 0) {
                swap(nums, p0, p1);
                p0++;
                p1++;
            } else if(nums[p1] == 1) {
                p1++;
            } else {
                swap(nums, p1, p2);
                p2--;
            }
        }
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    /**
     * 思路二：计数排序。统计数组中每种元素的数量，最后按数量重新赋值数组
     */
    public void sortColors2(int[] nums) {
        int[] colorNums = new int[3];
        for(int i = 0;i < nums.length;i++) {
            colorNums[nums[i]]++;
        }
        int p = 0;
        for(int color=0;color < colorNums.length;color++) {
            for(int j = p;j < p+colorNums[color];j++)
                nums[j] = color;
            p = p + colorNums[color];
        }
    }
}
